package 第九周;

/**
 * @author xhw
 */

public class 旋转链表 {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }

        // 定义一个指针用来遍历链表
        ListNode oldTail = head;
        int n;
        for (n = 1; oldTail.next != null; n++) {
            oldTail = oldTail.next;
        }
        // 形成环
        oldTail.next = head;

        // 新的尾部位置是在 n - k % n - 1
        // 新的头部位置是在 n - k % n
        ListNode newTail = head;
        for (int i = 0; i < n - k % n - 1; i++) {
            newTail = newTail.next;
        }
        ListNode newHead = newTail.next;

        // 断开环
        newTail.next = null;

        return newHead;
    }

    // 链表节点的定义
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {

    }
}